package com.coder.algorithm.offer_2;

import java.util.Arrays;

/**
 * 把数字翻译成字符串
 *
 * @author yuhushuan
 * @date 2020/6/27 10:08
 */
public class _46_1_TranslateNumbersToStrings {

    private static int getTranslationCount(int number) {
        if (number < 0) {
            return 0;
        }
        String strNumber = Integer.toString(number);
        return getTranslationCount(strNumber.toCharArray());
    }

    private static int getTranslationCount(char[] number) {
        int length = number.length;
        int[] counts = new int[length];
        int count = 0;

        // 从最小的子问题开始自下而上，消除重复的子问题
        for (int i = length - 1; i >= 0; --i) {
            count = 0;
            if (i < length - 1) {
                count = counts[i + 1];
            } else {
                count = 1;
            }
            if (i < length - 1) {
                int digit1 = number[i] - '0';
                int digit2 = number[i + 1] - '0';
                int converted = digit1 * 10 + digit2;

                if (converted >= 10 && converted <= 25) {
                    if (i < length - 2) {
                        count += counts[i + 2];
                    } else {
                        count += 1;
                    }
                }
            }
            counts[i] = count;
        }
        count = counts[0];
        System.out.println(Arrays.toString(counts));
        return count;
    }


    /**
     * 递归从在重复子问题
     *
     * @param number
     * @return
     */
    private static int getTranslationCount_solution2(int number) {
        if (number < 0) {
            return 0;
        }
        int len = 0;
        int temp = number;
        while (temp != 0) {
            len++;
            temp /= 10;
        }
        int[] numbers = new int[len];
        temp = number;
        while (temp != 0) {
            numbers[--len] = temp % 10;
            temp /= 10;
        }
        return getTranslationCountCore_solution2(numbers, 0);
    }

    private static int getTranslationCountCore_solution2(int[] numbers, int index) {
        if (numbers == null) {
            return 0;
        }
        // 遍历结束条件
        // 只有一位数字时，或者没有数字时，算一种翻译方法
        if (index >= numbers.length - 1) {
            return 1;
        }
        int result = 0;
        int converted = numbers[index] * 10 + numbers[index + 1];
        if (converted >= 10 && converted <= 25) {
            result = getTranslationCountCore_solution2(numbers, index + 1)
                    + getTranslationCountCore_solution2(numbers, index + 2);
        } else {
            result = getTranslationCountCore_solution2(numbers, index + 1);
        }
        return result;
    }

    public static void main(String[] args) {
        // 功能测试
        // 只有一位数字
        print(2);
        print(102);
        // 包含多位数字
        print(12258);
        print(120202);

        // 特殊输入测试
        // 负数
        print(-3232);
        // 包含25、26的数字
        print(12267);
    }

    private static void print(int number) {
        System.out.println("数字：" + number);
        System.out.println("解法一：共有 " + getTranslationCount(number) + " 中翻译方法。");
        System.out.println("解法二：共有 " + getTranslationCount_solution2(number) + " 中翻译方法。");
        System.out.println();
    }
}
